We prove lower bounds of order n log n for both the problem of multiplying polynomials of degree n, and of dividing polynomials with remainder, in the model of bounded coefficient arithmetic circuits over the complex numbers. These lower bounds are optimal up to order of magnitude. The proof uses a recent idea of R. Raz [Proc. 34th STOC 2002] proposed for matrix multiplication. It reduces the linear problem of multiplying a random circulant matrix with a vector to the bilinear problem of cyclic convolution. We treat the arising linear problem by extending J. Morgenstern's bound [J. ACM 20, pp. 305-306, 1973] in a unitarily invariant way. This establishes a new lower bound on the bounded coefficient complexity of linear forms in terms of the singular values of the corresponding matrix. In addition, we extend these lower bounds for linear and bilinear maps to a model of circuits that allows a restricted number of unbounded scalar multiplications.
展开▼
机译：在复数的有界系数算术电路模型中，我们证明了将n次多项式相乘以及将多项式除以余数的问题的n阶n log n下界。这些下限在数量级之前都是最佳的。该证明使用了R. Raz [Proc。第34届STOC 2002]提出用于矩阵乘法。它将随机循环矩阵与向量相乘的线性问题减少到循环卷积的双线性问题。我们通过扩展J. Morgenstern的界来处理出现的线性问题。 [ACM 20，第305-306页，1973]以一种不变的方式。就相应矩阵的奇异值而言，这为线性形式的有界系数复杂度建立了新的下界。另外，我们将线性和双线性映射的这些下界扩展到电路模型，该电路模型允许有限数量的无界标量乘法。
展开▼
